Publications HAL

2022

Article dans une revue

titre
PMNS for Efficient Arithmetic and Small Memory Cost
auteur
Fangan Yssouf Dosso, Jean-Marc Robert, Pascal Veron
article
IEEE Transactions on Emerging Topics in Computing, 2022, 10 (3), pp.1263 - 1277. ⟨10.1109/tetc.2022.3187786⟩
resume
The Polynomial Modular Number System (PMNS) is an integer number system which aims to speed up arithmetic operations modulo a prime p. Such a system is defined by a tuple (p, n, γ, ρ, E), where p, n, γ and ρ are positive integers, E ∈ Z[X], with E(γ) ≡ 0 (mod p). In [15] conditions required to build efficient AMNS (PMNS with E(X) = X n − λ, where λ ∈ Z \ {0}) are provided. In this paper, we generalise their approach for any monic polynomial E ∈ Z[X] of degree n. We present new bounds and highlight a set of polynomials E for very efficient operations in the PMNS and low memory requirement. We also provide AMNS and PMNS modular multiplication implementations, for a prime of size 256 bits, in classic C. We also provide, for the same prime, the first implementation taking advantage of the SIMD AVX512 instruction set. The AVX512 PMNS is 72 % faster than its AMNS counterpart (classical C version). This version presents a more than 60 % speed-up in comparison with the state-of-the-art Montgomery-CIOS modular multiplication of the GMP library.
typdoc
Article dans une revue
DOI
DOI : 10.1109/tetc.2022.3187786
Accès au texte intégral et bibtex
https://hal.science/hal-03768546/file/TETC3187786.pdf BibTex
titre
Faster multiplication over ${\mathbb {F}}_2[X]$ using AVX512 instruction set and VPCLMULQDQ instruction
auteur
Jean-Marc Robert, Pascal Véron
article
Journal of Cryptographic Engineering, 2022, ⟨10.1007/s13389-021-00278-3⟩
resume
Code-based cryptography is one of the main propositions for the post-quantum cryptographic context, and several protocols of this kind have been submitted on the NIST platform. Among them, BIKE and HQC are part of the five alternate candidates selected in the third round of the NIST standardization process in the KEM category. These two schemes make use of multiplication of large polynomials over binary rings, and due to the polynomial size (from 10,000 to 60,000 bits), this operation is one of the costliest during key generation, encapsulation, or decapsulation mechanisms. In BIKE-2, there is also a polynomial inversion which is time-consuming and this problem has been addressed in Drucker (Fast polynomial inversion for post quantum QC-MDPC cryptography, 2020). In this work, we revisit the different existing constant-time algorithms for arbitrary polynomial multiplication. We explore the different Karatsuba and Toom-Cook constructions in order to determine the best combinations for each polynomial degree range, in the context of AVX2 and AVX512 instruction sets. This leads to different kernels and constructions in each case. In particular, in the context of AVX512, we use the VPCLMULQDQ instruction, which is a vectorized binary polynomial multiplication instruction. This instruction deals with up to four polynomial (of degree up to 63) multiplications, that is four operand pairs of 64-bit words with 128-bit word storing each result, the four results being stored in one single 512-bit word. This allows to divide by roughly 3 the retired instruction number of the operation in comparison with the AVX2 instruction set implementations, while the speedup is up to 39% in terms of processor clock cycles. These results are different than the ones estimated in Drucker (Fast multiplication of binary polynomials with the forthcoming vectorized vpclmulqdq instruction, 2018). To illustrate the benefit of the new VPCLMULQDQ instruction, we used the HQC code to evaluate our approaches. When implemented in the HQC protocol, for the security levels 128, 192, and 256, our approaches provide up to 12% speedup, for key pair generation.
typdoc
Article dans une revue
DOI
DOI : 10.1007/s13389-021-00278-3
Accès au texte intégral et bibtex
https://cnrs.hal.science/hal-03520854/file/paper2cols.pdf BibTex

Communication dans un congrès

titre
A software comparison of RNS and PMNS
auteur
Laurent-Stephane Didier, Jean-Marc Robert, Fangan Yssouf Dosso, Nadia El Mrabet
article
ARITH29, Sep 2022, Virtual Conference, France. ⟨10.1109/arith54963.2022.00025⟩
resume
The Polynomial Modular Number System (PMNS) and the Residue Number System (RNS) are integer number systems which aim to speed up modular arithmetic. Their parallel properties make them suitable for the implementation of cryptographic applications on modern processors with SIMD instructions. In this work, we will show the implementation choices made for the modular multiplication in both systems and compare their implementation performances for several sizes of moduli. We target the Intel 64-bit sequential instruction set and the Intel AVX-512 vector instruction set. This instruction set allows significant speed-ups up to 1 621 bit size moduli, while the vectorized PMNS implementation is up to 2.5 times faster than the vectorized RNS, though the vectorized RNS becomes slightly better for 3 251 bits, due to the difficulty to find a PMNS with a suitable parameter n. The vectorized RNS implementations reach performance levels close the state-of-the-art GMP library, while the retired instruction counts are lower for sizes between 401 and 3 251 bits.
typdoc
Communication dans un congrès
DOI
DOI : 10.1109/arith54963.2022.00025
Accès au texte intégral et bibtex
https://cnrs.hal.science/hal-03916493/file/782700a086.pdf BibTex

2019

Article dans une revue

titre
Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding
auteur
Jean-Marc Robert, Christophe Negre, Thomas Plantard
article
Journal of Cryptographic Engineering, 2019, 9 (2), pp.115-136. ⟨10.1007/s13389-018-0196-7⟩
resume
Digital Signature Algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base Radix-R method and the Fixed-base Comb method. In this paper we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state of the art approaches.
typdoc
Article dans une revue
DOI
DOI : 10.1007/s13389-018-0196-7
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01926767/file/fixed-base-expo-and-scalar-mult-v19.pdf BibTex

2016

Communication dans un congrès

titre
Enhanced Digital Signature using RNS Digit Exponent Representation
auteur
Thomas Plantard, Jean-Marc Robert
article
WAIFI: Workshop on the Arithmetic of Finite Fields, Department of Mathematics of Ghent University, Jul 2016, Gand, Belgium. pp.177-192, ⟨10.1007/978-3-319-55227-9_13⟩
resume
Digital Signature Algorithm (DSA) involves modular expo-nentiation, of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers. However, due to the cost of the memory , to its small size and to the latency of access, previous research sought for minimization of the storage. In this paper, taking into account the modern processor features and the growing size of the cache memory, we improve the storage/efficiency trade-off, by using a RNS Digit exponent representation. We then propose algorithms for modular exponentiation. The storage is lower for equivalent complexities for modular exponenti-ation computation. The implementation performances show significant memory saving, up to 3 times for the largest NIST standardized key sizes compared to state of the art approaches.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-319-55227-9_13
Accès au texte intégral et bibtex
https://hal.science/hal-01337561/file/paper.pdf BibTex

2015

Article dans une revue

titre
New Parallel Approaches for Scalar Multiplication in Elliptic Curve over Fields of Small Characteristic
auteur
Christophe Negre, Jean-Marc Robert
article
IEEE Transactions on Computers, 2015, 64 (10), pp.2875-2890. ⟨10.1109/TC.2015.2389817⟩
resume
We present two new strategies for parallel implementation of scalar multiplication over elliptic curves. We first introduce a Montgomery-halving algorithm which is a variation of the original Montgomery point multiplication. This Montgomery-halving can be run in parallel with the original Montgomery point multiplication in order to concurently compute part of the scalar multiplication. We also present two point thirding formulas in some subfamily of curves E(GF(3^m)). We use these thirding formulas to implement the scalar multiplication through a Third-and-add approach and a parallel Third-and-add and Double-and-add or Triple-and-add approaches. We also provide some implementation results on an Intel Core i7 of the presented two strategies which show a speed-up of 5%-13% compared to non-parallelized approaches.
typdoc
Article dans une revue
DOI
DOI : 10.1109/TC.2015.2389817
Accès au texte intégral et bibtex
https://hal.science/hal-00908463/file/parallelization-ecsm8.pdf BibTex

Communication dans un congrès

titre
Parallel Approaches for Efficient Scalar Multiplication over Elliptic Curve
auteur
Christophe Negre, Jean-Marc Robert
article
SECRYPT 2015 - 12th International Conference on Security and Cryptography, Jul 2015, Colmar, France. pp.202-209, ⟨10.5220/0005512502020209⟩
resume
This paper deals with parallel implementation of scalar multiplication over an elliptic curve. We present parallel approaches which split the scalar into two parts for E(F_p) or three parts for E(F_{2^m}) and perform in parallel the scalar multiplication with each part of the scalar. We present timing results of these approaches implemented over an Intel Core i7 for NIST binary curves B233, B409 and for the twisted Edwards curve Curve25519. For the curves B409 and Curve25519 the proposed approaches improve by at least 10% the computation time of the scalar multiplication.
typdoc
Communication dans un congrès
DOI
DOI : 10.5220/0005512502020209
Accès au texte intégral et bibtex
https://hal.science/hal-01206530/file/parallelization-with-push5.pdf BibTex
titre
Efficient Modular Exponentiation Based on Multiple Multiplications by a Common Operand
auteur
Christophe Negre, Thomas Plantard, Jean-Marc Robert
article
ARITH: Computer Arithmetic, INRIA, Jun 2015, Lyon, France. pp.144-151, ⟨10.1109/ARITH.2015.24⟩
resume
The main operation in RSA encryption/decryption is the modular exponentiation, which involves a long sequence of modular squarings and multiplications. In this paper, we propose to improve modular multiplications AB, AC which have a common operand. To reach this goal we modify the Montgomery modular multiplication in order to share common computations in AB and AC. We extend this idea to reduce the cost of multiple modular multiplications AB1,. .. , AB by the same operand A. We then take advantage of these improvements in the Montgomery-ladder and SPA resistant m-ary exponentiation algorithms. The complexity analysis shows that for an RSA modulus of size 2048 bits, the proposed improvements reduce the number of word operations (ADD and MUL) by 14% for the Montgomery-ladder and by 5%-8% for the m-ary exponentiations. Our implementations show a speed-up by 8%-14% for the Montgomery-ladder and by 1%-8% for the m-ary exponentiations for modulus of size 1024, 2048 and 4048 bits.
typdoc
Communication dans un congrès
DOI
DOI : 10.1109/ARITH.2015.24
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01142327/file/exponentiation-with-optimized-montgomery16.pdf BibTex
titre
Recent Advances in Parallel Implementations of Scalar Multiplication over Binary Elliptic Curves
auteur
Christophe Negre, Jean-Marc Robert
article
RAIM: Rencontres Arithmétiques de l’Informatique Mathématique, A.Tisserand; D. Menard; S. Duquesne; S. Collange; N. SaintPierre, Apr 2015, Rennes, France
resume
The scalar multiplication is the main operation of cryptographic protocols based on elliptic curve. In the past few years, software implementations of scalar multiplication over binary elliptic curves have made some important progress. The new generations of Intel processors (Core i3,i5,7) provide a new instruction PCLMULQDQ which computes the product of 64bit binary polynomials which makes possible to speed-up the arithmetic in GF(2^m). The other improvements are due to new approaches for parallel implementation. We will review some recent results on parallel implementations based on GLV/GLS approach and on point halving.
typdoc
Communication dans un congrès
Accès au bibtex
BibTex

Thèse

titre
Contrer l'attaque Simple Power Analysis efficacement dans les applications de la cryptographie asymétrique, algorithmes et implantations
auteur
Jean-Marc Robert
article
Cryptographie et sécurité [cs.CR]. Université de Perpignan, 2015. Français. ⟨NNT : 2015PERP0039⟩
resume
Avec le développement des communications et de l'Internet, l'échange des informations cryptées a explosé. Cette évolution a été possible par le développement des protocoles de la cryptographie asymétrique qui font appel à des opérations arithmétiques telles que l'exponentiation modulaire sur des grands entiers ou la multiplication scalaire de point de courbe elliptique. Ces calculs sont réalisés par des plates-formes diverses, depuis la carte à puce jusqu'aux serveurs les plus puissants. Ces plates-formes font l'objet d'attaques qui exploitent les informations recueillies par un canal auxiliaire, tels que le courant instantané consommé ou le rayonnement électromagnétique émis par la plate-forme en fonctionnement.Dans la thèse, nous améliorons les performances des opérations résistantes à l'attaque Simple Power Analysis. Sur l'exponentiation modulaire, nous proposons d'améliorer les performances par l'utilisation de multiplications modulaires multiples avec une opérande commune optimisées. Nous avons proposé trois améliorations sur la multiplication scalaire de point de courbe elliptique : sur corps binaire, nous employons des améliorations sur les opérations combinées AB,AC et AB+CD sur les approches Double-and-add, Halve-and-add et Double/halve-and-add et l'échelle binaire de Montgomery ; sur corps binaire, nous proposons de paralléliser l'échelle binaire de Montgomery ; nous réalisons l'implantation d'une approche parallèle de l'approche Right-to-left Double-and-add sur corps premier et binaire, Halve-and-add et Double/halve-and-add sur corps binaire.
typdoc
Thèse
Accès au texte intégral et bibtex
https://theses.hal.science/tel-01269753/file/These_Robert_Jean-Marc_2015.pdf BibTex

2014

Communication dans un congrès

titre
Software Implementation of Parallelized ECSM over Binary and Prime Fields
auteur
Jean-Marc Robert
article
Inscrypt: Information Security and Cryptology, Dec 2014, Beijing, China. pp.445-462, ⟨10.1007/978-3-319-16745-9_24⟩
resume
Recent developments of multicore architectures over various platforms (desktop computers and servers as well as embedded systems) challenge the classical approaches of sequential computation algorithms, in particular elliptic curve cryptography protocols. In this work, we deploy different parallel software implementations of elliptic curve scalar multiplication of point, in order to improve the performances in comparison with the sequential counter parts, taking into account the multi-threading synchronization, scalar recoding and memory management issues. Two thread and four thread algorithms are tested on various curves over prime and binary fields, they provide improvement ratio of around 15% with best their sequential counterparts.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-319-16745-9_24
Accès au texte intégral et bibtex
https://hal.science/hal-00998277/file/paper.pdf BibTex
titre
Algorithmes Parallèles de Multiplication Scalaire Optimisée sur Courbes Elliptiques Binaires
auteur
Jean-Marc Robert
article
C2: Journées Codage et Cryptographie, GT-C2, Mar 2014, Les Sept-Laux, France
resume
La démocratisation des processeurs multic\oe urs ainsi que les implémentations matérielles permettent l'utilisation d'algorithmes parallèles pour effectuer toutes sortes de calculs. Dans le cas des calculs cryptographiques sur courbes elliptiques, les protocoles actuels utilisent principalement la multiplication par un scalaire de points de la courbe. Pour ces derniers calculs, les approches parallèles aujourd'hui se limitent essentiellement à des approches \emph{Double-Halve-and-add}, qui nécessitent un recodage du scalaire permettant un lancement en parallèle de deux calculs partiels et indépendants (respectivement \emph{Double-and-add} et \emph{Halve-and-add}). Ceci n'est possible que sur les systèmes cryptographiques basés sur les courbes elliptiques binaires (caractéristique $2$). Après avoir présenté cette approche, nous exposerons les résultats de nos travaux dans deux directions nouvelles : - la parallélisation d'algorithmes type échelle binaire de Montgomery, présentant l'avantage d'une résistance intrinsèque à certaines attaques par canal auxiliaire ; - des algorithmes concurrents effectuant en parallèle les doublements ou divisions par deux des points, et les additions correspondantes. Dans cet exposé, nous parlerons de l'élaboration et de la validation des algorithmes, ainsi que des performances des implémentations logicielles réalisées, confrontées à l'état de l'art publié à ce jour. Nous concluerons sur les développements futurs et les applications possibles de ces algorithmes.
typdoc
Communication dans un congrès
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01121960/file/JC2_03-2014.pdf BibTex

2013

Communication dans un congrès

titre
Impact of Optimized Operations AB,AC and AB+CD in Scalar Multiplication over Binary Elliptic Curve
auteur
Christophe Negre, Jean-Marc Robert
article
AFRICACRYPT: Cryptology in Africa, Jun 2013, Cairo, Egypt. pp.13-30, ⟨10.1007/978-3-642-38553-7_16⟩
resume
A scalar multiplication over a binary elliptic curve consists in a sequence of hundreds of multiplications, squarings and additions. This sequence of eld operations often involves a large amount of operations of type AB,AC and AB+CD. In this paper, we modify classical polynomial multiplication algorithms to obtain optimized algorithms which perform these particular operations AB,AC and AB+CD. We then present software implementation results of scalar multiplication over binary elliptic curve over two platforms: Intel Core 2 and Intel Core i5. These experimental results show some signi cant improvements in the timing of scalar multiplication due to the proposed optimizations.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-642-38553-7_16
Accès au texte intégral et bibtex
https://inria.hal.science/hal-00724785/file/africacrypt13-scalar-mul-with-abpluscd11.pdf BibTex

Poster de conférence

titre
État Des Lieux Attaques Passives Courbes Elliptiques
auteur
Jean-Marc Robert
article
EJCIM: École Jeunes Chercheurs en Informatique Mathématique, Apr 2013, Perpignan, France. , 2013
resume
Lors de protocoles cryptographiques sur courbe elliptique (par exemple, un échange de clé de Diffie-Hellmann), la principale opération effectuée est la multiplication scalaire de points de la courbe. Cette opération est susceptible d'être attaquée par Simple Power Analysis et Differential Power Analysis (basées sur la mesure de la puissance électrique du calculateur, par exemple, lors d'un ou plusieurs calculs). Dans ce poster, nous présentons les algorithmes et les principales contre-mesures. Nous concluons sur nos travaux en cours.
typdoc
Poster de conférence
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00862374/file/EJCIM2013.pdf BibTex

2012

Communication dans un congrès

titre
Algorithmes et Implémentations Optimisées de Calculs Cryptographiques sur les Courbes Elliptiques Binaires
auteur
Jean-Marc Robert
article
C2: Journées Codage et Cryptographie, GT-C2, Oct 2012, Dinard, France
resume
Les calculs cryptographiques nécessitent d’effectuer des opérations sur des corps finis avec les règles arithmétiques correspondantes. Le développement de la cryptographie sur les courbes elliptiques (ECC, Elliptic Curve Cryptography), et plus particulièrement celles définies sur les corps binaires (F 2 m ), implique d’implémenter ces opérations à l’aide d’algorithmes de plus en plus performants, et de tirer parti des plates-formes disposant des processeurs ayant un jeu d’instruction étendu à l’arithmétique des polynômes de ces corps binaires. Après avoir rappelé les fondements de l’arithmétique sur les courbes elliptiques ainsi que pour les opérations sur les corps binaires, nous parlerons ensuite d’optimisations du code exploitant les spécificités du processeur Intel Core I7, en particulier la multiplication sans retenue (carry-less multiplier ), ainsi que l’utilisation des registres MMX (MultiMedia eXtension). Ces deux optimisations impliquent une refonte profonde de la façon de coder les algorithmes, de par le caractère SIMD du jeu d’instruction correspondant. Nous montrerons combien les algorithmes doivent être adaptés à de tels types de variables. Ces implémentations permettent d’atteindre les meilleures performances publiées et d’être au niveau de l’état de l’art. Peut-on aller plus loin ? Certaines combinaisons d’opérations sur le corps binaire (F 2 m ), lorsque des opérandes sont communes ou donnent lieu à des simplifications, peuvent-elles apporter un gain supplémentaire ? L’examen d’optimisations prenant en compte des opérations combinées de type AB, AC et AB + CD, (A, B, C, D ∈ F 2 m ) fait l’objet d’expérimentations. La combinatoire des cas (taille des corps binaires finis et type des variables manipulées par les implémentations) est partiellement explorée. Des gains sont observés sous certaines conditions. Les expérimentations menées laissent encore la question ouverte, mais tracent la voie à des développements ultérieurs.
typdoc
Communication dans un congrès
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01121958/file/C2-111012.pdf BibTex